package com.example.practice.one;

/**
 * description:
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
 * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * <p>
 * 因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
 * 跳1级，剩下n-1级，则剩下跳法是f(n-1)
 * 跳2级，剩下n-2级，则剩下跳法是f(n-2)
 * 所以f(n)=f(n-1)+f(n-2)+...+f(1)
 * 因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
 * 所以f(n)=2*f(n-1)
 * <p>
 * author: bowen
 * date: 2019/6/21
 */
public class Test09 {
    public int JumpFloorII(int target) {
        if (target <= 2) {
            return target;
        }
        int t = 2;
        for (int i = 3; i <= target; i++) {
            t *= 2;
        }
        return t;
    }

    public int JumpFloorII2(int target) {
        return 1 << (target - 1);
    }

    public static void main(String[] args) {
        Test09 t = new Test09();
        System.out.println(t.JumpFloorII2(5));
    }
}
